package com.tgy.algorithm.base;

import java.util.Arrays;

public class _快速排序_02 {

    public static void quickSort(int[] nums) {
        doQuickSort(nums, 0, nums.length - 1);
    }

    public static void doQuickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int povit = nums[right];
        int preIndex = left - 1;
        int curIndex = left;
        while (curIndex < right) {
            // 这边必须加上等号，要把相等的value放到preIndex的左边
            if (nums[curIndex] <= povit) {
                if(preIndex + 1 != curIndex) {
                    swap(nums, preIndex + 1, curIndex);
                }
                preIndex++;
            }
            curIndex++;
        }

        swap(nums,preIndex + 1,right);
        doQuickSort(nums,left,preIndex);
        doQuickSort(nums,preIndex + 2,right);
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,1,5,4,3,6};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
